package tree.segmenttree;

/**
 * @Classname : RangeSumQueryMutable
 * @Description : 307. 区域和检索 - 数组可修改
 * https://leetcode.cn/problems/range-sum-query-mutable/
 * @Author : chentianyu
 * @Date 2022/12/6 00:42
 */

/**
 * 方法一：分块处理
 */
public class RangeSumQueryMutable {
    // 数组
    private int[] nums;
    // 数组元素个数
    private int n;
    // 记录每段范围内数字之和
    private int[] sums;
    // 分段元素个数
    private int size;

    public RangeSumQueryMutable(int[] nums) {
        this.nums = nums;
        n = nums.length;
        size = (int) Math.sqrt(n);
        // + size - 1 保证，哪怕余1也会分段个数加1
        sums = new int[(n + size - 1) / size];
        for (int i = 0; i < n; i++) {
            sums[i / size] += nums[i];
        }
    }

    public void update(int index, int val) {
        // 更新目标段之和
        sums[index / size] += (val - nums[index]);
        // 更新目标位置元素
        nums[index] = val;
    }

    public int sumRange(int left, int right) {
        int[] sums = this.sums;
        int a = left / size, b = right / size, sum = 0;
        // 在同一段内的情况
        if (a == b) {
            for (int i = left; i <= right; i++) {
                sum += nums[i];
            }
            return sum;
        }
        // 不在同一段内的情况，分三次计算
        for (int i = left; i < (a + 1) * size; i++) {
            sum += nums[i];
        }
        for (int i = a + 1; i < b; i++) {
            sum += sums[i];
        }
        for (int i = b * size; i <= right; i++) {
            sum += nums[i];
        }
        return sum;
    }
}  // end class
